package com.jiang.daily.Q3297;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/09 1:44
 */
class Solution {
    public long validSubstringCount(String word1, String word2) {
        int[] diff = new int[26]; // 用来表示word2中每个字母出现次数
        for (char c: word2.toCharArray()) {
            diff[c - 'a']--;
        }
        int cnt = (int) Arrays.stream(diff).filter(c -> c < 0).count(); // 统计word2中出现了几个不同的字母，当word2中某个字母在word1的子字符串中出现了相同次数，则cnt--
        int l = 0;
        int r = 0;
        int len = word1.length();
        long res = 0;

        // l 和 r表示这个窗口
        while (l < len) {
            // 当r走到最后或者窗口中包含word2全部字母，则退出循环
            while (r < len && cnt != 0) {
                // 不属于word2的字母在diff一定大于或等于0，属于word2的字母在diff一定小于或等于0
                if (++diff[word1.charAt(r) - 'a'] == 0) {
                    cnt--; // 属于word2的某个字母在窗口中出现相同次数, cnt--
                }
                r++;
            }

            // 如果窗口中包含word2全部字母，就统计从r - 1前面开始到len全部子串可能
            if (cnt == 0) {
                res += len - r + 1;
            }


            // 现在就要将窗口缩小，就是l++, 如果在l的字母是word2中出现的，在新的窗口这个字母出现的次数比在word2中出现的次数少1，那么diff[l]--(小于0,等于-1), cnt++；没出现，那么diff[l]--(大于等于0)
            if(--diff[word1.charAt(l) - 'a'] == -1) {
                cnt++;
            }
            l++;
        }
        return res;
    }
}
